public class BM14 {

    public class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode oddEvenList (ListNode head) {
        // write code here
        if(head == null || head.next == null) return head;
        ListNode odd = new ListNode(0);ListNode oddTail = odd;
        ListNode even = new ListNode(0);ListNode evenTail = even;
        ListNode cur = head;
        boolean isOdd = true; // 用于判断当前节点是奇数位还是偶数位
        while(cur != null){
            if (isOdd) {
                oddTail.next = cur; // 将当前节点连接到奇数位链表上
                oddTail = cur; // 更新奇数位链表的尾节点
            } else {
                evenTail.next = cur; // 将当前节点连接到偶数位链表上
                evenTail = cur; // 更新偶数位链表的尾节点
            }
            cur = cur.next;
            isOdd = !isOdd; // 切换奇偶数位
        }
        //注意：：！！！链表尾部置空
        evenTail.next = null;

        oddTail.next = even.next;
        return odd.next;
    }
}
